const graph = [
  [0, 2, 4, 0, 0, 0],
  [0, 0, 2, 4, 2, 0],
  [0, 0, 0, 0, 3, 0],
  [0, 0, 0, 0, 0, 2],
  [0, 0, 0, 3, 0, 2],
  [0, 0, 0, 0, 0, 0]
];

const INF = Number.MAX_SAFE_INTEGER;
const minDistance = (dist, visited) => {
  let min = INF;
  let minIndex = -1;
    for (let v = 0; v < dist.length; v++) {
    if (visited[v] === false && dist[v] <= min) {
      min = dist[v];
      minIndex = v;
    }
  }
  return minIndex;
};
/**
 * @Author: zxc
 * @Date: 2020-08-15 12:17:35
 * 首先，在这里先将所有的路径置为无限大
 * 然后，将所有顶点的标识置为false
 * 1. 将其对应的自己的路径长度置为0
 * 2. 循环遍历，一共六个点，遍历0-4，5位置因为没有后续所以不用遍历
 * 3. 通过minDistance方法找到最小路径点的位置
 * 4. 将这个位置在visited中置为true
 * 5. 遍历总长度0-5
 * 6. 如果当时位置visited中为false,并且它在图中有权值，并且dist中这个位置不是无限大，并且 dist[u]+图中当前的u对应的这个位置 < dist中这个位置的值
 * 7. 这个位置在dist中的值换成dist[u] + graph[u][v]
 * 8. dist中存放的某点至其它点的最短路径了
 */
export const dijkstra = (graph, src) => {
  const dist = [];
  const visited = [];
  const { length } = graph;
  for (let i = 0; i < length; i++) {
    dist[i] = INF;
    visited[i] = false;
  }
  dist[src] = 0;
  for (let i = 0; i < length; i++) {
    const u = minDistance(dist, visited);
    visited[u] = true;
    console.log(u,dist,visited)
    for (let v = 0; v < length; v++) {
      console.log(v+"---"+u, dist[u] ,graph[u][v] ,dist[v])
      if (!visited[v] && graph[u][v] !== 0 && dist[u] !== INF && dist[u] + graph[u][v] < dist[v]) {
        console.log(v)
        dist[v] = dist[u] + graph[u][v];
      }
    }
  }
  return dist;
};

var dist = dijkstra(graph, 0);
console.log(dist)
for (let i = 0; i < dist.length; i++){
    console.log(i + '\t\t' + dist[i]);
}
